package net.fkrahe.graph;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;

/**
 * Class Graph
 * 
 * @author @author Yedidyah Langsan | Moshe Augenstein | Aaron M. Tenenbaum
 */
public class Graph {

    protected LinkedList<GraphNode> graphNodes;

    public Graph() {
        graphNodes = new LinkedList<GraphNode>();
    }

    /**
     * Adds the specified graph node to the graph. If another node
     * with the same name is already on the graph, the method does
     * nothing and returns false.
     * 
     * @param infoObj
     * @return true if node is inserted 
     */
    public boolean add(Object infoObj) {
        if (findNode(infoObj) != null) {
            return false;
        }
        GraphNode gn = new GraphNode(infoObj);
        graphNodes.addLast(gn);
        return true;
    }

    /**
     * Returns an Iterator of the names of all the nodes info-Objects in this graph
     * 
     * @return an Iterator of the names of all the nodes info-Objects in this graph
     */
    public Iterator nodes() {
        ArrayList<Object> al = new ArrayList<Object>();
        Iterator en = graphNodes.iterator();
        while (en.hasNext()) {
            GraphNode gn = (GraphNode) en.next();
            al.add(gn.getInfo());
        }
        return al.iterator();
    }

    /**
     * Returns true if node1 is adjacent to node2
     * 
     * @param infoObj1
     * @param infoObj2
     * @return 
     */
    public boolean adjacent(Object infoObj1, Object infoObj2) {
        GraphNode gn1 = findNode(infoObj1);
        GraphNode gn2 = findNode(infoObj2);
        LinkedList<ArcNode> arcList = gn1.getArcptr();

        // if arcList is null, then node1 is not adjacent to anything
        if (arcList == null) {
            return false;
        }

        // search the arcList for node2
        Iterator<ArcNode> itrAn = arcList.iterator();
        while (itrAn.hasNext()) {
            ArcNode an = (ArcNode) itrAn.next();
            if (an.getPtr() != null && an.getPtr() == gn2) {
                return true;
            }
        }
        return false;
    }

    /**
     * Searches the list of graph nodes for one for wich name == 
     * graphNode.info(). If such a node cannot be found, the method
     * return null.
     * 
     * @param infObject
     * @return 
     */
    public GraphNode findNode(Object infObject) {
        int index = graphNodes.indexOf(new GraphNode(infObject));
        if (index >= 0) {
            return (GraphNode) graphNodes.get(index);
        } else {
            return null;
        }
    }

    /**
     * Returns a String with each node's info .toString()
     * and each node's ArcNode .toString()
     * 
     * @return 
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("$ Nodes ").append(graphNodes.toString()).append("\n");
        Iterator<GraphNode> itrGn = graphNodes.iterator();
        while (itrGn.hasNext()) {
            GraphNode gn = itrGn.next();
            sb.append(gn.getInfo().toString()).append("\n");
            LinkedList<ArcNode> arcList = gn.getArcptr();
            if (arcList == null) {
                continue;
            }
            Iterator<ArcNode> itrAn = arcList.iterator();
            while (itrAn.hasNext()) {
                ArcNode an = itrAn.next();
                sb.append(an.toString()).append("\n");
            }
        }
        return sb.toString();
    }
}
